/**
 * 给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
 * <p>
 * '.' 匹配任意单个字符
 * '*' 匹配零个或多个前面的那一个元素
 * 所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
 * <p>
 * 说明:
 * <p>
 * s 可能为空，且只包含从 a-z 的小写字母。
 * p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
 * 示例 1:
 * <p>
 * 输入:
 * s = "aa"
 * p = "a"
 * 输出: false
 * 解释: "a" 无法匹配 "aa" 整个字符串。
 * 示例 2:
 * <p>
 * 输入:
 * s = "aa"
 * p = "a*"
 * 输出: true
 * 解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
 * 示例 3:
 * <p>
 * 输入:
 * s = "ab"
 * p = ".*"
 * 输出: true
 * 解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
 * 示例 4:
 * <p>
 * 输入:
 * s = "aab"
 * p = "c*a*b"
 * 输出: true
 * 解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
 * 示例 5:
 * <p>
 * 输入:
 * s = "mississippi"
 * p = "mis*is*p*."
 * 输出: false
 */
class RegularExpression {

    public static void main(String[] args) {
        System.out.println(RegularExpression.isMatch("aa", "a"));//false
        System.out.println(RegularExpression.isMatch("aaa", "aaaa"));//false
        System.out.println(RegularExpression.isMatch("aa", "a*"));///true
        System.out.println(RegularExpression.isMatch("ab", ".*"));//true
        System.out.println(RegularExpression.isMatch("aab", "c*a*b"));//true
        System.out.println(RegularExpression.isMatch("aaa", "a*a"));//true
        System.out.println(RegularExpression.isMatch("mississippi", "mis*is*p*."));//false

        /*System.out.println(RegularExpression.isMatch("aba", ".*a"));//true
        System.out.println(RegularExpression.isMatch("aba", ".*b"));//false
        System.out.println(RegularExpression.isMatch("aba", ".*b.*a"));//true
        System.out.println(RegularExpression.isMatch("aba", ".*ba"));//true
        System.out.println(RegularExpression.isMatch("aba", ".*ab"));//false
        System.out.println(RegularExpression.isMatch("abab", ".*ab"));//true
        System.out.println(RegularExpression.isMatch("ab", ".*c"));//false*/
    }

    /**
     * 用递归的方法去处理这个（还是有很多很多判断）
     *
     * @param s
     * @param p
     * @return
     */
    public static boolean isMatch(String s, String p) {
        //异常判断
        if (null == s || null == p || s.length() == 0 || p.length() == 0 || p.equals("*")) {
            return false;
        }
        return myMatch(s, p);
    }


    /**
     * 用递归的方法去处理这个
     *
     * @param s
     * @param p
     * @return
     */
    public static boolean myMatch(String s, String p) {
        //异常判断
        if (null == s || null == p || p.length() == 0 || p.startsWith("*")) {
            return false;
        }
        char[] chars = s.toCharArray();
        char[] pattern = p.toCharArray();
        int patternLen = p.length();
        //分几种情况，处理完某一种情况之后递归去处理下面的情况

        //开头是非.和非*的字符
        if (pattern[0] != '.' && pattern[0] != '*') {
            //1、非.和非*的字符，如果结束了或者后一个不是*
            if (patternLen == 1 || pattern[1] != '*') {
                if (chars.length == 0) {//如果已经结束
                    return false;
                } else if (chars[0] == pattern[0]) { //对比两个字符串的开头
                    if (patternLen == 1 && chars.length == 1) {//如果都结束了
                        return true;
                    } else {//如果匹配还没结束就递归下去
                        return myMatch(s.substring(1), p.substring(1));
                    }
                } else {
                    return false;
                }
            }

            //2、非.和非*的字符，且后一个是*，且再后面没了
            if (pattern[1] == '*' && patternLen == 2) {
                return true;
            }

            //3、非.和非*的字符，且后一个是*，且再后面和这个字符不一样
            if (pattern[1] == '*' && pattern[0] != pattern[2]) {
                for (int i = 0; i < chars.length; i++) {
                    if (chars[i] != pattern[0]) {//一旦发现不是当前字符的情况就递归下去
                        return myMatch(s.substring(i), p.substring(2));
                    }
                }
            }

            //4、非.和非*的字符，且后一个是*，且再后面和这个字符一样
            if (pattern[1] == '*' && pattern[0] == pattern[2]) {
                //需要再向后找有多少这种情况
                int special = 2;
                while (special + 1 > patternLen) {//在越界的情况下
                    if (pattern[special] == pattern[special + 1]) {
                        special++;
                    } else {
                        break;
                    }
                }
                //算出需要至少匹配多少个该字符，即size
                int size = special - 1;
                for (int i = 0; i < chars.length; i++) {
                    if (chars[i] == pattern[0]) {//发现是当前字符的情况
                        size--;
                    } else {//发现不是当前字符的情况
                        if (size <= 0) {//如果size小于等于0表示匹配成功，递归下去
                            return myMatch(s.substring(i), p.substring(special + 1));
                        } else {  //否则没匹配完成
                            return false;
                        }
                    }
                }
                //如果全部匹配结束
                if (special + 1 == patternLen) {//如果表达式已经结束
                    return true;
                } else {//否则以空字符串递归下去
                    return myMatch("", p.substring(special + 1));
                }
            }
        }

        //开头是.
        if (pattern[0] == '.') {
            //5、开头是.，且没有后一个
            if (patternLen == 1) {
                if (chars.length == 1) {
                    return true;
                } else {
                    return false;
                }
            }

            //6、开头是.，且一个不是*
            if (pattern[1] != '*') {
                return myMatch(s.substring(1), p.substring(1));
            }

            //7、开头是.，且后一个是*，且后面没字符串了
            if (pattern[1] == '*' && patternLen == 2) {
                return true;
            }

            //8、开头是.，且后一个是*，且后面有字符串
            if (pattern[1] == '*' && patternLen >= 2) {
                //需要分很多种情况
                return true;
            }
        }
        return true;
    }


}